package class06


/*
	给定一个只由0（假）、1（真）、&（逻辑与）、|（逻辑或）和^（异或）物种字符串组成的
	字符串express，再给定一个布尔值desired。返回express能有多少种组合方式，可以达到
	desired的结果。
	【举例】
	express = “1^0|0|1”，desired = false
	只有1^((0|0)|1)和1^(0|(0|1))的组合可以得到false，返回2。express="1"
	desired = false, 无组合则可以到false，返回0

	思路：
		范围上的尝试模型，设定递归函数fn(L, R, desired)
		含义是：再L...R的范围上，组合后的答案为 desired，组合的总数
		则可能性有：
			1. desired 等于 true
				1.1 i位置进行分割，i为&
				1.2 i位置进行分割，i为^
				1.3 i位置进行分割，i为|
		    2. desired 等于 false
				2.1 i位置进行分割，i为&
				2.2 i位置进行分割，i为^
				2.3 i位置进行分割，i为|

		转化为dp动态转移方程解法时，需要注意将三个参数分为两张表，一张为true表，一张为false表
		true表：L 为 纵坐标， R为横坐标， false 表建立同理
			0 1 2 3 4 5 6 // 长度必须为奇数, R
		0	b x ? x ? x ? // L=R 需要填写，base case
		1	x x x x x x x // row无需填，因为不存在该情况
		2	x x b x ? x ? // col奇数列无需填写，因为不可能以符号为结尾
		3	x x x x x x x // row无需填，因为不存在该情况
		4	x x x x b x ?
		5	x x x x x x x // row无需填，因为不存在该情况
		6	x x x x x x b


*/
func num1(express string, desired bool) int {
	if express == "" {
		return 0
	}
	if !IsValid(express) {
		return 0
	}
	return ExpressProcess(express, 0, len(express)-1, desired)
}

func ExpressProcess(express string, L, R int, desired bool) int {
	if L == R {
		if desired {
			if express[L] == '1' {
				return 1
			}
			return 0
		} else {
			if express[L] == '1' {
				return 0
			}
			return 1
		}
	}
	var res int
	var a, b, c, d int
	if desired {
		for i:=L+1; i<=R; i=i+2 {
			switch express[i] {
			case '|':
				a = ExpressProcess(express, L, i-1, true)
				b = ExpressProcess(express, L, i-1, false)
				c = ExpressProcess(express, i+1, R, true)
				d = ExpressProcess(express, i+1, R, false)
				res = res + a*c + a*d + b*c
			case '^':
				a = ExpressProcess(express, L, i-1, true)
				b = ExpressProcess(express, L, i-1, false)
				c = ExpressProcess(express, i+1, R, true)
				d = ExpressProcess(express, i+1, R, false)
				res = res + a*d + b*c
			case '&':
				a = ExpressProcess(express, L, i-1, true)
				c = ExpressProcess(express, i+1, R, true)
				res = res + a*c
			}
		}
	} else {
		for i:=L+1; i<=R; i=i+2 {
			switch express[i] {
			case '|':
				b = ExpressProcess(express, L, i-1, false)
				d = ExpressProcess(express, i+1, R, false)
				res = res + b*d
			case '^':
				a = ExpressProcess(express, L, i-1, true)
				b = ExpressProcess(express, L, i-1, false)
				c = ExpressProcess(express, i+1, R, true)
				d = ExpressProcess(express, i+1, R, false)
				res = res + a*c + b*d
			case '&':
				a = ExpressProcess(express, L, i-1, true)
				b = ExpressProcess(express, L, i-1, false)
				c = ExpressProcess(express, i+1, R, true)
				d = ExpressProcess(express, i+1, R, false)
				res = res + a*d + b*d + b*c
			}
		}
	}
	return res
}

func IsValid(express string) bool {
	if len(express) & 1 == 0 { // 字符长度为奇数
		return false
	}
	for i:=0; i<len(express); i=i+2 {
		if !(express[i] == '1' ||  express[i] == '0') {
			return false
		}
	}
	for i:=1; i<len(express); i=i+2 {
		if !(express[i] == '|' ||  express[i] == '&' || express[i] == '^') {
			return false
		}
	}
	return true
}

func num2(express string, desired bool) int {
	tMap := make([][]int, len(express))
	fMap := make([][]int, len(express))

	for i:=0; i<len(express); i++ {
		tMap[i] = make([]int, len(express))
		fMap[i] = make([]int, len(express))
	}
	for i:=0; i<len(express); i=i+2 {
		if express[i] == '1' {
			fMap[i][i] = 0
			tMap[i][i] = 1
		} else {
			fMap[i][i] = 1
			tMap[i][i] = 0
		}
	}
	/*
			true表：L 为 纵坐标， R为横坐标， false 表建立同理
			0 1 2 3 4 5 6 // 长度必须为奇数, R
		0	b x ? x ? x ? // L=R 需要填写，base case
		1	x x x x x x x // row无需填，因为不存在该情况
		2	x x b x ? x ? // col奇数列无需填写，因为不可能以符号为结尾
		3	x x x x x x x // row无需填，因为不存在该情况
		4	x x x x b x ?
		5	x x x x x x x // row无需填，因为不存在该情况
		6	x x x x x x b
	*/
	for L:=len(express)-3; L>=0; L = L-2 {
		for R:= L+2; R<=len(express); R = R+2 {
			for i:=L+1; i<len(express); i++ {
				switch express[i] {
				case '|':
					tMap[L][R] += tMap[L][i-1]*tMap[i+1][R]
					tMap[L][R] += tMap[L][i-1]*fMap[i+1][R]
					tMap[L][R] += fMap[L][i-1]*tMap[i+1][R]
				case '^':
					tMap[L][R] += tMap[L][i-1]*fMap[i+1][R]
					tMap[L][R] += fMap[L][i-1]*tMap[i+1][R]
				case '&':
					tMap[L][R] +=  tMap[L][i-1]*tMap[i+1][R]
				}
				switch express[i] {
				case '|':
					fMap[L][R] += fMap[L][i-1]*fMap[i+1][R]
				case '^':
					fMap[L][R] += tMap[L][i-1]*tMap[i+1][R]
					fMap[L][R] += fMap[L][i-1]*fMap[i+1][R]
				case '&':
					fMap[L][R] +=  tMap[L][i-1]*fMap[i+1][R]
					fMap[L][R] +=  fMap[L][i-1]*fMap[i+1][R]
					fMap[L][R] +=  fMap[L][i-1]*tMap[i+1][R]
				}
			}
		}
	}
	if desired {
		return tMap[0][len(express)-1]
	}
	return fMap[0][len(express)-1]
}